package com.captain.leetcode2.链表;

import com.captain.leetcode.链表.ListNode;
import org.w3c.dom.NodeList;

import java.util.List;

/**
 * Des:
 * <p>
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置
 * <p>
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[4,5,1,2,3]
 * <p>
 * 输入：head = [0,1,2], k = 4
 * 输出：[2,0,1]
 *
 * @author XL
 * @Date 2021/8/31 10:51
 */
public class 旋转链表61 {
    public static void main(String[] args) {
        new 旋转链表61().rotateRight(ListNode.getInstance(), 2);
    }

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) return null;
        ListNode loop = head;
        int len = 0;
        //获取长度
        while (loop != null) {
            loop = loop.next;
            len++;
        }
        if (k == len) return head;
        //避免循环 取模
        k = k % len;
        if (k == 0) return head;
        //1.获取倒数第n的链表  len - index = k
        // 5 - 2 - 1 = 2
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy.next;
        // 1 2
        int index = 0;
        while (cur.next != null) {
            if (len - index - 1 == k) {
                break;
            }
            index++;
            cur = cur.next;
        }
        ListNode back = cur.next == null ? cur : cur.next;
        cur.next = null;
        ListNode pre = dummy.next;
        dummy.next = back;
        while (back.next != null) {
            back = back.next;
        }
        back.next = pre;
        return dummy.next;
    }
}
